package LeetCode.LC34;

/**
 * 34. 在排序数组中查找元素的第一个和最后一个位置
 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 * 你的算法时间复杂度必须是 O(log n) 级别。
 * 如果数组中不存在目标值，返回 [-1, -1]。
 * @author corn
 * @create 2020-11-03-13:44
 */
public class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] targetRange = {-1, -1};

        int left = extremeInsertionIndex(nums, target, true);
        if (left == nums.length || nums[left] != target) {
            return targetRange;
        }

        targetRange[0] = left;
        targetRange[1] = extremeInsertionIndex(nums, target, false) - 1;

        return targetRange;
    }
    private int extremeInsertionIndex(int[] nums, int target, boolean left) {
        int l = 0;
        int r = nums.length;

        while (l < r) {
            int mid = (l + r) / 2;
            //大于或相等且取最左边
            if (nums[mid] > target || (left && target == nums[mid])) {
                r = mid;
            }
            else {
                l = mid+1;
            }
        }
        return l;
    }
}
